import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/*
*
* 算法：迭代
*
* 需求：给一个根节点，要求进行前序遍历
*
* 思路：
* 1. 对于任意节点，先 add 节点入 list ，入栈；
* 2. 然后判断左侧子节点是否为空，不为空，指针指向左子节点，入栈，进入下一次循环；
* 3. 如果左子节点为空，判断右子节点是否为空，不为空，入栈，指针指向右子节点，进入下一次循环；
* 4. 如果右子节点为空，出栈，指针指向出站后栈顶，继续判断右子节点
*
*
*
* */
public class Solution_2 {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> resultList = new ArrayList<>();
        if(root==null)
        {
            return resultList;
        }
        // 建栈
        Stack<TreeNode> stack = new Stack<>();

        // 建立指针
        TreeNode point = root;

        // 开始循环
        while(point!=null)
        {
            //当前指针不为空，推指针入栈
            stack.push(point);
            //添加指针值的结果列表
            resultList.add(point.val);
            //如果左子节点不为空
            if(point.left!=null)
            {
                //指针指向左子节点，开启下一次循环
                point=point.left;
            }
            //左子节点为空，则判断右子节点
            else {
                if(stack.empty())
                {
                    break;
                }
                //如果右子节点为空
                while (point.right==null)
                {
                    //出栈
                    stack.pop();
                    if(!stack.empty()) {//指向当前栈顶
                        point = stack.peek();
                    }
                    else {
                        point=null;
                        break;
                    }
                }
                if(point!=null) {
                    //右子节点不为空
                    //指针指向右子节点，开启下一次循环
                    // 当前节点出栈
                    stack.pop();
                    point = point.right;
                }
            }
        }

        return resultList;
    }
}
